📈 최대 부분 증가 수열 (LIS: Longest Increasing Subsequence)

1️⃣ 개념

"주어진 수열에서 일부 원소를 선택해서 만들 수 있는 증가하는 부분 수열 중 가장 긴 것의 길이"

배열 안에서 값이 점점 커지는 형태로 이어지는 부분만 뽑았을 때,
그 길이가 가장 긴 경우를 구하는 문제입니다.

🧐 예시

입력: [10, 20, 10, 30, 20, 50]

가능한 증가 부분 수열 중 일부는 👇

• [10, 20, 30, 50] → 길이 4 ✅

• [10, 20, 50] → 길이 3

• [10, 30, 50] → 길이 3

따라서 정답은 4 🎯

2️⃣ 핵심 아이디어

각 원소를 기준으로,

"이 원소로 끝나는 증가 수열의 최대 길이"
를 구해서 배열에 저장합니다.

🧠 점화식

dy[i] = arr[i]를 마지막 원소로 하는 LIS의 길이

dy[i] = max(dy[j] + 1) (단, arr[j] < arr[i] 인 모든 j < i 에 대해)

현재 값보다 작은 이전 원소들 중에서,
가장 긴 수열 길이를 찾아 + 1 해주는 방식입니다.

3️⃣ 예시 풀이

function LIS(arr) {
	const n = arr.length;
	const dy = Array.from({ length: n }, () => 1); // 최소 길이 1

	for (let i = 0; i < n; i++) {
		for (let j = i - 1; j >= 0; j--) {
			if (arr[i] > arr[j]) {
				dy[i] = Math.max(dy[j] + 1, dy[i]);
			}
		}
	}

	return Math.max(...dy);
}

console.log(LIS([10, 20, 10, 30, 20, 50])); // ✅ 출력: 4

💡 dy 배열이 채워지는 과정